package com.atguigu.tree;

import lombok.Getter;
import lombok.Setter;
/*
本例中的二叉树不是二叉排序树！！
 */
public class BinaryTreeDemo {

  public static void main(String[] args) {
    // 先需要创建一颗二叉树
    BinaryTree binaryTree = new BinaryTree();
    // 创建需要的结点
    HeroNode root = new HeroNode(1, "宋江");
    HeroNode node2 = new HeroNode(2, "吴用");
    HeroNode node3 = new HeroNode(3, "卢俊义");
    HeroNode node4 = new HeroNode(4, "林冲");
    HeroNode node5 = new HeroNode(5, "关胜");

    // 说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
    root.setLeft(node2);
    root.setRight(node3);
    node3.setRight(node4);
    node3.setLeft(node5);
    binaryTree.setRoot(root);

    // 测试一把删除结点

    System.out.println("删除前,前序遍历");
    binaryTree.preOrder(); //  1,2,3,5,4
    binaryTree.delNode(5);
    // binaryTree.delNode(3);
    System.out.println("删除后，前序遍历");
    binaryTree.preOrder(); // 1,2,3,4
  }
}

// 定义BinaryTree 二叉树
@Setter
class BinaryTree {
  private HeroNode root;
  // 删除结点
  public void delNode(int no) {
    if (root != null) {
      // 如果只有一个root结点, 这里立即判断root是不是就是要删除结点
      if (root.getNo() == no) {
        root = null;
      } else {
        // 调用HeroNode的方法，以该节点为跟向下搜索no并删除
        root.delNode(no);
      }
    } else {
      System.out.println("空树，不能删除~");
    }
  }
  // 前序遍历，其实就是调用HeroNode的方法，没什么好看的
  public void preOrder() {
    if (this.root != null) {
      this.root.preOrder();
    } else {
      System.out.println("二叉树为空，无法遍历");
    }
  }
}

@Getter
@Setter
class HeroNode { // 二叉树上保存的节点数据
  private int no; // no,name都是数据
  private String name;
  private HeroNode left; // 默认null
  private HeroNode right; // 默认null

  public HeroNode(int no, String name) {
    this.no = no;
    this.name = name;
  }

  @Override
  public String toString() {
    return "HeroNode [no=" + no + ", name=" + name + "]";
  }

  // 递归删除结点
  // 1.如果删除的节点是叶子节点，则删除该节点
  // 2.如果删除的节点是非叶子节点，则删除该子树
  public void delNode(int no) {
    // 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
    if (this.left != null && this.left.no == no) {
      this.left = null;
      return;
    }
    // 3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
    if (this.right != null && this.right.no == no) {
      this.right = null;
      return;
    }
    // 4.我们就需要向左子树进行递归删除
    if (this.left != null) {
      this.left.delNode(no);
    }
    // 5.则应当向右子树进行递归删除
    if (this.right != null) {
      this.right.delNode(no);
    }
  }

  // 编写前序遍历的方法
  public void preOrder() {
    System.out.println(this); // 先输出父结点
    // 递归向左子树前序遍历
    if (this.left != null) {
      this.left.preOrder();
    }
    // 递归向右子树前序遍历
    if (this.right != null) {
      this.right.preOrder();
    }
  }
  // 中序遍历
  public void infixOrder() {

    // 递归向左子树中序遍历
    if (this.left != null) {
      this.left.infixOrder();
    }
    // 输出父结点
    System.out.println(this);
    // 递归向右子树中序遍历
    if (this.right != null) {
      this.right.infixOrder();
    }
  }
  // 后序遍历
  public void postOrder() {
    if (this.left != null) {
      this.left.postOrder();
    }
    if (this.right != null) {
      this.right.postOrder();
    }
    System.out.println(this);
  }
}
